package impl.sort;

import anaydis.sort.SorterType;

import java.util.Comparator;
import java.util.List;

/**
 * Created by IntelliJ IDEA.
 * User: Tomi
 * Date: 01/09/2011
 * Time: 16:27:53
 * To change this template use File | Settings | File Templates.
 */
public class QuickSorter extends AbstractSorter {
    public QuickSorter() {
        super(SorterType.QUICK);
    }
    public <T> void sort(Comparator<T> c, List<T> list) {
        sort(c, list, 0, list.size()-1);
    }
    private <T> void sort(Comparator<T> c, List<T> list, int l, int r) {
        if(l<r){
            int pivot = r;
            int i = l;
            int j = pivot-1;
            while(i!=j){
                while((!greater(c, list, i, pivot))&&(i<j)){
                    i++;
                }
                while((greater(c, list, j, pivot))&&(j>i)){
                    j--;
                }
                if(i!=j){
                    swap(list, i, j);
                }
            }
            if(greater(c, list, i, pivot)){
                swap(list, pivot, i);
            }else if(i!=pivot-1){
                return;
            }
            if(i==pivot-1){
                sort(c, list, l, pivot-1);
            }else{
                sort(c, list, l, i-1);
                sort(c, list, i+1, r);
            }
        }
    }
}